package LC;

/**
 * https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/
 * Follow up for problem "Populating Next Right Pointers in Each Node".
 * What if the given tree could be any binary tree? Would your previous solution still work?
 * Note:
 * You may only use constant extra space.
 * For example,
 * Given the following binary tree,
 * 1
 * /  \
 * 2    3
 * / \    \
 * 4   5    7
 * After calling your function, the tree should look like:
 * 1 -> NULL
 * /  \
 * 2 -> 3 -> NULL
 * / \    \
 * 4-> 5 -> 7 -> NULL
 */
public class LC_117_PopulatingNextRightPointersinEachNodeII_LinkedBinaryTree {
    public static void main(String[] args) {

    }

    static class TreeLinkNode {
        int val;
        TreeLinkNode left, right, next;

        TreeLinkNode(int x) {
            val = x;
        }
    }

    static class Solution {
        static void connect(TreeLinkNode root) {
            if (root != null)
                dfs(root, root.left, root.right);
        }

        private static void dfs(TreeLinkNode parent, TreeLinkNode leftchild, TreeLinkNode rightchild) {
            TreeLinkNode p = parent;
            while (p.next != null && (p == parent || (p.left == null && p.right == null)))
                p = p.next;
            if (leftchild != null) {
                if (rightchild != null)
                    leftchild.next = rightchild;
                else {
                    if (p != parent)
                        leftchild.next = p.left != null ? p.left : p.right;
                }
            }
            if (rightchild != null) {
                if (p != parent)
                    rightchild.next = p.left != null ? p.left : p.right;
            }
            if (rightchild != null)
                dfs(rightchild, rightchild.left, rightchild.right);
            if (leftchild != null)
                dfs(leftchild, leftchild.left, leftchild.right);
        }
    }
}
